package com.wtgroup.demo.leetcode.q060_排列序列_第k个排列;

/**
 * dfs+剪枝法
 * https://leetcode-cn.com/problems/permutation-sequence/solution/hui-su-jian-zhi-python-dai-ma-java-dai-ma-by-liwei/
 * 1ms, 99.96%
 * 效率: 10分; 逻辑: 10分;
 */
public class Q060_LC_B_Dfs {

    /*
    执行用时：
    1 ms
    , 在所有 Java 提交中击败了
    99.96%
    的用户
    内存消耗：
    35.8 MB
    , 在所有 Java 提交中击败了
    73.82%
    的用户
    */

    int[] factorial;

    public String getPermutation(int n, int k) {
        factorial = calcFactorial(n - 1);

        StringBuilder path = new StringBuilder(n);
        boolean[] used = new boolean[n+1];
        dfs(n, path, 1, used, k);

        return path.toString();
    }

    private void dfs(int n, StringBuilder path, int depth, boolean[] used, int k) {


        for (int i = 1; i <= n; i++) {
            if(used[i]) continue;
            // 剪纸
            if (k > factorial[n - depth]) {
                k -= factorial[n - depth];
                continue;
            }
            path.append(i);
            used[i] = true;
            dfs(n, path, depth+1, used, k);
            // 无需回溯
            return;
        }
    }

    private int[] calcFactorial(int x) {
        int[] ints = new int[x + 1];
        ints[0] = 1;
        for (int i = 1; i <= x; i++) {
            ints[i] = i * ints[i - 1];
        }
        return ints;
    }



}
